package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2020/7/17 16:05
 */
public class Scramble {
    /**
     * 扰乱字符串
     * 给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。
     * 在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。
     */
    @Test
    public void isScramble() {
        Assert.assertTrue(isScramble("abcde", "abced"));
        Assert.assertTrue(isScramble("great", "rgeat"));
        Assert.assertFalse(isScramble("abcde", "caebd"));
        Assert.assertTrue(isScramble2("abcde", "abced"));
        Assert.assertTrue(isScramble2("great", "rgeat"));
        Assert.assertFalse(isScramble2("abcde", "caebd"));
    }

    public boolean isScramble2(String s1, String s2) {
        // TODO 没看懂
        char[] chs1 = s1.toCharArray();
        char[] chs2 = s2.toCharArray();
        int n = s1.length();
        int m = s2.length();
        if (n != m) {
            return false;
        }
        boolean[][][] dp = new boolean[n][n][n + 1];
        // 初始化单个字符的情况
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][1] = chs1[i] == chs2[j];
            }
        }

        // 枚举区间长度 2～n
        for (int len = 2; len <= n; len++) {
            // 枚举 S 中的起点位置
            for (int i = 0; i <= n - len; i++) {
                // 枚举 T 中的起点位置
                for (int j = 0; j <= n - len; j++) {
                    // 枚举划分位置
                    for (int k = 1; k <= len - 1; k++) {
                        // 第一种情况：S1 -> T1, S2 -> T2
                        if (dp[i][j][k] && dp[i + k][j + k][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                        // 第二种情况：S1 -> T2, S2 -> T1
                        // S1 起点 i，T2 起点 j + 前面那段长度 len-k ，S2 起点 i + 前面长度k
                        if (dp[i][j + len - k][k] && dp[i + k][j][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }

    public boolean isScramble(String s1, String s2) {
        // 特殊情况处理
        if (s1 == null || s2 == null) {
            return s1 == s2;
        }
        if (s1.length() != s2.length()) {
            return false;
        }

        // dfs
        return dfs(s1, s2, 0, 0, s1.length());
    }

    private boolean dfs(String s1, String s2, int i, int j, int l) {
        // 递归终止条件
        if (l == 1) {
            return s1.charAt(i) == s2.charAt(j);
        }

        // 剪枝
        int[] tmp = new int[26];
        for (int k = 0; k < l; k++) {
            tmp[s1.charAt(i + k) - 'a']++;
            tmp[s2.charAt(j + k) - 'a']--;
        }
        for (int c : tmp) {
            if (c != 0) {
                return false;
            }
        }

        // 递归
        for (int k = 1; k < l; k++) {
            if (dfs(s1, s2, i, j, k) && dfs(s1, s2, i + k, j + k, l - k)) {
                return true;
            }
            if (dfs(s1, s2, i, j + l - k, k) && dfs(s1, s2, i + k, j, l - k)) {
                return true;
            }
        }

        // 返回
        return false;
    }
}
